<!DOCTYPE html>
<html>

<head>
<meta charset="UTF-8">

<title> 【NOI2018】归程 - 题目 - Judge Duck Online </title>

<link rel="icon" type="image/png" href="/images/judgeduck-logo-small.png" />

<script src="/libs/js/jquery-3.2.1.min.js"></script>

<!-- Latest compiled and minified CSS -->
<link rel="stylesheet" href="/libs/css/bootstrap.min.css" />

<!-- Latest compiled and minified JavaScript -->
<script src="/libs/js/bootstrap.min.js"></script>

<link rel="stylesheet" type="text/css" href="/css/main.css" />
<link rel="stylesheet" href="/css/non-responsive.css" type="text/css" />

<script src="/js/md5.js"></script>
<script src="/js/judgeduck.js"></script>

<script type="text/x-mathjax-config">
	MathJax.Hub.Config({
		showProcessingMessages: false,
		tex2jax: {
			inlineMath: [["$", "$"], ["\\\\(", "\\\\)"]],
			processEscapes:true
		},
		menuSettings: {
			zoom: "Hover"
		}
	});
</script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS_HTML"></script>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.css">
<script src="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.js"></script>

</head>

<body onload="">

<!-- Fixed navbar -->
<nav class="navbar navbar-default" role="navigation" style="background-color: #eeeeee">
	<div class="container">
		<div class="navbar-header">
			<div class="navbar-brand">
				<a href="/">
					<img src="/images/judgeduck-logo.png" width="40px" height="40px" style="margin:-10px" />
				</a>
			</div>
			<font class="navbar-brand">
				Judge Duck Online
			</font>
		</div>
		<div class="navbar-collapse collapse">
			<ul class="nav navbar-nav">
				<li class="nav-item">
					<a class="nav-link" href="/index/index.html"> 首页 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/problems/index.html"> 题目列表 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/submissions/index.html"> 提交记录 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/blogs/index.html"> 博客 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/faq/index.html"> FAQ </a>
<a href="http://www.iis7.com" id="fd5181b16e1e4bf28f11699efa99c2a2" style="display:inline-block;background-color:;color:#fff;padding:2px 5px;font-family:arial;font-size:12px;font-weight:bold;" target="_blank" class="fd5181b16e1e4bf28f11699efa99c2a2" >iis7站长之家</a>
				</li>
			</ul>
			<ul class="nav navbar-nav navbar-right">
				<li class="nav-item">
					<a class="nav-link" href="/user/login/index.html"> 登录 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/user/register/index.html"> 注册 </a>
				</li>
			</ul>
		</div><!--/.nav-collapse -->
	</div>
</nav>




<div id="main_div" class="container" style="padding-left: 25px; padding-right: 25px">
<h2> 【NOI2018】归程 <a href='/problem/noi18a/board/index.html' class=' pull-right btn btn-success'> 排行榜 </a> </h2><hr />时间限制： 4 s <br />空间限制： 512 MB <br /><br /><h3>题目背景</h3>

<p>本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。</p>

<p>魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的<strong>无向连通图</strong>（节点的编号从 $1$ 至 $n$）。我们依次用 $l,a$ 描述一条边的<strong>长度</strong>、<strong>海拔</strong>。</p>

<p>作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此<strong>有积水的边一定是海拔相对最低的一些边</strong>。</p>

<p>我们用<strong>水位线</strong>来描述降雨的程度，它的意义是：所有海拔<strong>不超过</strong>水位线的边都是<strong>有积水</strong>的。</p>

<h3>题目描述</h3>

<p>Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。</p>

<p>Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的水位线 $p$。</p>

<p>每一天，Yazid 在出发点都拥有一辆<strong>车</strong>。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。</p>

<ul>
<li><p>需要特殊说明的是，第二天车会被重置，这意味着：</p>

<ul>
<li><p>车会在新的出发点被准备好。</p></li>
<li><p>Yazid 不能利用之前在某处停放的车。</p></li>
</ul></li>
</ul>

<p>Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他<strong>步行经过的</strong>边的总长度。请你帮助 Yazid 进行计算。</p>

<p><em>本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。</em></p>

<h3>输入格式</h3>

<p>从标准输入读入数据。</p>

<p>单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$，表示数据的组数。接下来依次描述每组数据，对于每组数据：</p>

<ul>
<li><p>第一行 $2$ 个非负整数 $n,m$，分别表示节点数、边数。</p></li>
<li><p>接下来 $m$ 行，每行 $4$ 个正整数 $u,v,l,a$，描述一条连接节点 $u,v$ 的、长度为 $l$、海拔为 $a$ 的边。</p>

<ul>
<li>在这里，我们保证 $1\leq u,v\leq n$。</li>
</ul></li>
<li><p>接下来一行 $3$ 个非负数 $Q,K,S$，其中 $Q$ 表示总天数，$K\in\left\{0,1\right\}$ 是一个会在下面被用到的系数，$S$ 表示的是可能的最高水位线。</p></li>
<li><p>接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0,p_0$ 描述一天：</p>

<ul>
<li><p>这一天的出发节点为 $v=\left(v_0+K\times lastans-1\right)\bmod n+1$。</p></li>
<li><p>这一天的水位线为 $p=\left(p_0+K\times lastans\right)\bmod \left(S+1\right)$。</p></li>
<li><p>其中 $lastans$ 表示上一天的答案（最小步行总路程）。特别地，我们规定第 $1$ 天时 $lastans=0$。</p></li>
<li><p>在这里，我们保证 $1\leq v_0\leq n$，$0\leq p_0\leq S$。</p></li>
</ul></li>
</ul>

<p>对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。</p>

<h3>输出格式</h3>

<p>输出到标准输出。</p>

<p>依次输出各组数据的答案。对于每组数据：</p>

<ul>
<li>输出 $Q$ 行每行一个整数，依次表示每天的最小步行总路程。</li>
</ul>

<h3>样例一</h3>

<h4>输入</h4>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="12" style="background-color:white" readonly>1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2
</textarea>
</div>

<p></div></p>

<h4>输出</h4>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="6" style="background-color:white" readonly>0
50
200
50
150
</textarea>
</div>

<p></div></p>

<h4>解释</h4>

<p>第一天没有降水，Yazid 可以坐车直接回到家中。</p>

<p>第二天、第三天、第四天的积水情况相同，均为连接 $1,2$ 号节点的边、连接 $3,4$ 号点的边有积水。</p>

<p>对于第二天，Yazid 从 $2$ 号点出发坐车只能去往 $3$ 号节点，对回家没有帮助。因此 Yazid 只能纯靠徒步回家。</p>

<p>对于第三天，从 $4$ 号节点出发的唯一一条边是有积水的，车也就变得无用了。Yazid 只能纯靠徒步回家。</p>

<p>对于第四天，Yazid 可以坐车先到达 $2$ 号节点，再步行回家。</p>

<p>第五天所有的边都积水了，因此 Yazid 只能纯靠徒步回家。</p>

<h3>样例二</h3>

<h4>输入</h4>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="13" style="background-color:white" readonly>1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0
</textarea>
</div>

<p></div></p>

<h4>输出</h4>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="5" style="background-color:white" readonly>0
2
3
1
</textarea>
</div>

<p></div></p>

<h4>解释</h4>

<p>本组数据强制在线。</p>

<p>第一天的答案是 $0$，因此第二天的 $v=\left( 5+0-1\right)\bmod 5+1=5$，$p=\left(2+0\right)\bmod\left(3+1\right)=2$。</p>

<p>第二天的答案是 $2$，因此第三天的 $v=\left( 2+2-1\right)\bmod 5+1=4$，$p=\left(0+2\right)\bmod\left(3+1\right)=2$。</p>

<p>第三天的答案是 $3$，因此第四天的 $v=\left( 4+3-1\right)\bmod 5+1=2$，$p=\left(0+3\right)\bmod\left(3+1\right)=3$。</p>

<h3>子任务</h3>

<p><em>所有测试点均保证 $T\leq 3$，所有测试点中的所有数据均满足如下限制：</em></p>

<ul>
<li><p>$n\leq 2\times 10^5$，$m\leq 4\times 10^5$，$Q\leq 4\times 10^5$，$K\in\left\{0,1\right\}$，$1\leq S\leq 10^9$。</p></li>
<li><p>对于所有边：$l\leq 10^4$，$a\leq 10^9$。</p></li>
<li><p>任意两点之间都直接或间接通过边相连。</p></li>
</ul>

<p><strong>为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：</strong></p>

<ul>
<li><p>图形态：对于表格中该项为“一棵树”或“一条链”的测试点，保证 $m=n-1$。除此之外，这两类测试点分别满足如下限制：</p>

<ul>
<li><p>一棵树：保证输入的图是一棵树，即保证边不会构成回路。</p></li>
<li><p>一条链：保证所有边满足 $u+1=v$。</p></li>
</ul></li>
<li><p>海拔：对于表格中该项为“一种”的测试点，保证对于所有边有 $a=1$。</p></li>
<li><p>强制在线：对于表格中该项为“是”的测试点，保证 $K=1$；如果该项为“否”，则有 $K=0$。</p></li>
<li><p>对于所有测试点，如果上述对应项为“不保证”，则对该项内容不作任何保证。</p></li>
</ul>

<table class="table table-bordered"><thead><tr><th rowspan="1">$n$</th><th rowspan="1">$m$</th><th rowspan="1">$Q=$</th><th rowspan="1">测试点</th><th rowspan="1">图形态</th><th rowspan="1">海拔</th><th rowspan="1">强制在线</th></tr></thead><tbody><tr><td rowspan="1">$\leq 1$</td><td rowspan="1">$\leq 0$</td><td rowspan="1">$0$</td><td rowspan="1">1</td><td rowspan="6">不保证</td><td rowspan="6">一种</td><td rowspan="10">否</td></tr><tr><td rowspan="1">$\leq 6$</td><td rowspan="1">$\leq 10$</td><td rowspan="1">$10$</td><td rowspan="1">2</td></tr><tr><td rowspan="1">$\leq 50$</td><td rowspan="1">$\leq 150$</td><td rowspan="1">$100$</td><td rowspan="1">3</td></tr><tr><td rowspan="1">$\leq 100$</td><td rowspan="1">$\leq 300$</td><td rowspan="1">$200$</td><td rowspan="1">4</td></tr><tr><td rowspan="1">$\leq 1500$</td><td rowspan="1">$\leq 4000$</td><td rowspan="1">$2000$</td><td rowspan="1">5</td></tr><tr><td rowspan="1">$\leq 200000$</td><td rowspan="1">$\leq 400000$</td><td rowspan="1">$100000$</td><td rowspan="1">6</td></tr><tr><td rowspan="3">$\leq 1500$</td><td rowspan="5">$=n-1$</td><td rowspan="3">$2000$</td><td rowspan="1">7</td><td rowspan="3">一条链</td><td rowspan="14">不保证</td></tr><tr><td rowspan="1">8</td></tr><tr><td rowspan="1">9</td></tr><tr><td rowspan="5">$\leq 200000$</td><td rowspan="5">$100000$</td><td rowspan="1">10</td><td rowspan="2">一棵树</td></tr><tr><td rowspan="1">11</td><td rowspan="1">是</td></tr><tr><td rowspan="3">$\leq 400000$</td><td rowspan="1">12</td><td rowspan="9">不保证</td><td rowspan="3">否</td></tr><tr><td rowspan="1">13</td></tr><tr><td rowspan="1">14</td></tr><tr><td rowspan="2">$\leq 1500$</td><td rowspan="2">$\leq 4000$</td><td rowspan="2">$2000$</td><td rowspan="1">15</td><td rowspan="6">是</td></tr><tr><td rowspan="1">16</td></tr><tr><td rowspan="4">$\leq 200000$</td><td rowspan="4">$\leq 400000$</td><td rowspan="2">$100000$</td><td rowspan="1">17</td></tr><tr><td rowspan="1">18</td></tr><tr><td rowspan="2">$400000$</td><td rowspan="1">19</td></tr><tr><td rowspan="1">20</td></tr></tbody></table> 

<p><strong>为了优化你的阅读体验，我们在表格中把测试点的编号放在了中间，请注意这一点。</strong></p>

<h3>题目来源</h3>

<p>NOI 2018 Day 1</p>
<hr />
				<div class="row">
					<input type="hidden" id="pid" value="noi18a" />
					<div class="col-xs-3 form-group">
						<label for="language"> 语言 </label>
						<select class="form-control" id="language">
							<option> C </option>
<option selected> C++ </option>
<option> C++11 </option>
						</select>
					</div>
					<div class="col-xs-12 form-group">
						<h4>关于标准输出的说明（最后更新：2018年10月23日）</h4>

<p>标准输出将被重定向到内存中，所以你的内存使用量也包括了你的标准输出的大小（向上取整到 4KB 的倍数）。</p>

<p>如果你的程序要进行大量输出，请考虑这一点。</p>

					</div>
					<div class="col-xs-12 form-group">
						<label for="code"> 你的代码 </label>
						<textarea id="code" class="form-control" rows="10">#include &lt;stdio.h&gt;

int main() {
	return 0;
}
</textarea>
						<br />
					</div>
					<div class="col-xs-12 form-group">
						<a href="javascript:judgeduck.submit()" id="btn_submit" class="btn btn-md btn-default"> 提交 </a>
					</div>
					<br />
				</div>

	<hr />
	
	<div class="row">
		<p style="text-align: center; color: #888">
			Judge Duck Online | 评测鸭在线 <br />
			Server Time: 2019-08-02 17:11:13 | Loaded in 0 ms | <a href="/status/index.html"> Server Status </a> <br />
			个人娱乐项目，仅供学习交流使用
		</p>
	</div>
</div>

</body>

</html>
